#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int INF=0x3f3f3f3f;
int d[6][6]={{0,0,0,0,0,0},{0,0,2,INF,1,8},{0,6,0,3,2,INF},{0,INF,INF,0,4,INF},{0,INF,INF,2,0,3},{0,3,INF,INF,INF,0}};
int n=5;
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main(){
  floyd();
  for(int i=1;i<=5;++i){
    for(int j=1;j<=5;++j){
      printf("%-20d",d[i][j]);
    }
    cout<<endl;
  }
  return 0;
}
// int main(){
//   int weight[5]={3,2,1,4,5};
//   int value[5]={25,20,15,40,50};
//   int maxweight=6;
//   vector<vector<int>> dp(6,vector<int>(maxweight+1,0));
//   //dp[i][j]表示在前i个物品中选择不超过j重量的最大价值
//   for(int i=1;i<=5;++i){
//     for(int j=0;j<=maxweight;++j){
//       dp[i][j]=dp[i-1][j];//第i个物品选
//       if(j-weight[i-1]>=0){//不选
//         dp[i][j]=max(dp[i][j],dp[i-1][j-weight[i-1]]+value[i-1]);
//       }
//     }
//   }
//   cout<<dp[5][maxweight]<<endl;
//   return 0;
// }
